Round Overview
Discuss this match
This one is mainly an implementation problem. We need to convert the input 64 bits number to hexadecimal, but replacing 1 and 0 with uppercase ‘I’ and ‘O’, respectively. We also need to detect when digits from 2 to 9 are used and return error.
Converting to hexadecimal is a common task that tends to be implemented in the programming language’s standard libraries. So we can try to use those implementations. This does bring some complications because those conversions tend to represent their output by starting with and “0x” or might use lower case letters instead of uppercase. We can just remove the additional characters and convert to uppercase. The result can look very simple like the following python solution:
1
2
3
4
5
6
7
8
9
10
11
12
class Hexspeak:
def decode(self, ciphertext):
s = hex(ciphertext) # convert to hex
s = s[2: -1] # Remove leading 0x and trailing L
s = s.upper() # convert to upper
case
s = s.replace('1', 'I') # replace 1 with I,
s = s.replace('0', 'O') # and 0 with O
if any((ch in "23456789") for ch in s): #Check fo invalid digits
return "Error!"
return s
Dealing with the specifics of the standard hex conversion might be too much trouble since we can just extract the digits ourselves. We just need to use an usual base conversion by successive division algorithm. Each digit would be between 0 and 15, we can convert it to a letter (if valid) or return “Error!” if invalid. This approach does bring a small corner case when the integer is 0, however:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
string decode(long ciphertext) {
if (ciphertext == 0) {
return "O";
}
// We can use a std::map to decide which digit is what letter:
// this can be replaced with a select case / if then else
map < int, char > digit_to_letter = {
{
0,
'O'
},
{
1,
'I'
},
{
10,
'A'
},
{
11,
'B'
},
{
12,
'C'
},
{
13,
'D'
},
{
14,
'E'
},
{
15,
'F'
},
};
string s = "";
// extract digits:
while (ciphertext > 0) {
int d = ciphertext % 16;
ciphertext /= 16;
// if digit not in table, it is invalid
if (digit_to_letter.count(d) == 0) {
return "Error!";
} else {
// else add the digit, note the order:
s = digit_to_letter[d] + s;
}
}
return s;
}
This is a problem that has flexibility in the result. The tree we output can have any configuration as long as it is a tree, has exactly `n` nodes and `m` leaves. It’s worth noticing that the constraints forbid `n < 3`, and `m` will always be strictly smaller than `n`.
Given that flexibility we need to think of a method to generate those trees that is as simple to implement as possible. Since we can assume `n > m`, then there is always at least one node that we can use as root. Let’s label the root 0. Imagine it is initially connected to the `m` leaves:
There are `n - m - 1` additional non-leaves that we need to add. A simple method is to add them between the root and one of the leaves. This guarantees that the added nodes do not become leaves. The root will have multiple children (`n = 3`) so it will not be a leaf either.
We just need to build this tree. We can use labels `0` to `n-m-1` for the nodes that are not leaves. Then we add the leaves starting with index `n-m`, then `n-m+1` and so and so:
1
2
3
4
5
6
7
8
9
10
11
12
13
vector < int > getTree(int n, int m) {
vector < int > res;
for (int i = 0; i < n - m - 1; i++) {
res.push_back(i);
res.push_back(i + 1);
}
for (int i = 0; i < m; i++) {
res.push_back(0);
res.push_back(n - m + i);
}
return res;
}
One thing that is very helpful in this problem is that the maximum number of points is 3. So let’s first tackle the 3-point version.
Imagine `R` was a valid safety level. This would mean that the curve would never get within `R` distance units to any of the points. Take each of the points and color all the points that are within `r` distance units and what we get is 3 disks:
So we need to find the maximum `R` such that we can draw a path starting at point `(0,0)` and ending at point `(10^100, 0)` without crossing any circle of radius `R` centered at each of the input points.
Let’s deal with the `(10^100, 0)` part. `10^100` is a very large number in comparison to the constraints of the input in this problem. Problem writer might have as well said “very large”, infinite, `oo` , etc. We also have plenty of freedom in the curve that we draw connecting the two points. The way to interpret this, is that as long as we can draw a path that gets as far away as possible from all of the circles, we can then do anything we want from a large enough distance from the circles and reach `(10^100, 0)`. So what we worry about is that point `(0,0)` shouldn’t be enclosed by the circles. The following is a simple case:
In this case, one of the circles is already large enough that it contains point `(0,0)`, no matter what we do with the path, the starting point of the path already overlaps with a disk. So we wouldn’t be able to find a correct curve.
The following case is more complicated:
The origin `(0,0)` is now surrounded by the disks. Even though none of the disks overlaps with `(0,0)`, it is still impossible to make a correct path to `(10^100, 0)`.
But this scenario is tricky to detect. First of all, note how the following version still allows a valid curve:
Two of the circles just touch but don’t overlap; Are perfectly tangent. We can just draw a line that crosses through their intersection point.
Another case is like this:
The 3 circles overlap, but the origin is outside the part that the circles enclose.
In order to detect if the origin would be trapped by the circles, we can imagine a triangle connecting the 3 points. If the origin is inside this triangle, then having the circles overlap with each other would trap the origin.
I made an interactive applet that lets you play with the circles and the intersections and makes the properties more visible:
We just need to turn what we learned into a solution. We want to maximize `R`. First of all, none of the circles must contain the origin `(0,0)`. A circle contains the origin if the Euclidean distance from its center to `(0,0)` is greater than `R`. Let’s name `bar(AO)`, `bar(BO)` and `bar(CO)` the respective distances from the points to the origin. Then `R` needs to pass the following conditions:
`R <= bar(AO)`
`R <= bar(BO)`
`R <= bar(CO)`
Also, in case there are 3 points and the origin lies inside the triangle made by the 3 points, we also need to have at least one pair of circles that don’t overlap. They may touch but not overlap. The at least part is important, it is possible that two of the pairs of circles overlap but one doesn’t.
Consider points `A` and `B`. Their distance is `bar(AB)`, note that we have two circles of radius `R` centered at those points. Do they overlap? This happens when `2R > bar(AB)`. So we add an additional condition, at least one of the following must be true:
`R <= bar(AB)/2`
`R <= bar(BC)/2`
`R <= bar(AC)/2`
Since only one of these conditions needs to be true, we can take the maximum out of `bar(AB), bar(BC), bar(AC)` and then:
`R <= (max(bar(AB), bar(BC), bar(AC)))/2`
This condition and the ones above need to be true. They are all less than conditions so we need to take the minimum:
`R <= min((max(bar(AB), bar(BC), bar(AC)))/2, bar(AO), bar(BO), bar(CO))`
This is in case there are 3 points and the origin is inside the triangle. In other case it would just be the minimum of the distances to the origin. You can analyze the 2-points , 1-point cases yourself, the only way to have an overlap with the path is if the circles themselves overlap with the origin.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// Finds twice the signed area of a triangle (using cross product)
// the sign of the area tells us if the points are in clockwise or anti-clockwise
// direction. If the area is 0, they are colinear.
long area2(long x1, long y1, long x2, long y2, long x3, long y3) {
// Returns 2 * area of the triangle using cross product.
// If the result is negative, the points are in anti-clockwise order.
// If the result is 0, the points are collinear.
return (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
}
bool triangle_contains_origin(vector < int > x, vector < int > y) {
// This can be tricky because the problem statmeent makes no restrictions
// on these points. They can be colinear. There can be duplicate points
// We don't know if they are in clockwise or anti-clockwise order.
// The method to do this check should be robust and able to deal with
// those corner cases. Or we can deal with the corner cases separately.
long s1 = area2(x[0], y[0], x[1], y[1], 0, 0);
long s2 = area2(x[1], y[1], x[2], y[2], 0, 0);
long s3 = area2(x[2], y[2], x[0], y[0], 0, 0);
// All signs must be equal.
if ((s1 > 0) && (s2 > 0) && (s3 > 0)) {
return true;
}
if ((s1 < 0) && (s2 < 0) && (s3 < 0)) {
return true;
}
return false;
}
double maximalSafetyLevel(vector < int > x, vector < int > y) {
double mind = 1e100;
// minimum distance from origing to each point:
for (int i = 0; i < x.size(); i++) {
double dx = x[i], dy = y[i];
mind = std::min(mind, sqrt(dx * dx + dy * dy));
}
// the special case:
if ((x.size() == 3) && triangle_contains_origin(x, y)) {
double tm = 0.0;
// find the half of the maximum distance between two points
// max(AB,BC,AC) / 2
for (int i = 0; i < 3; i++) {
for (int j = i + 1; j < 3; j++) {
double dx = x[i] - x[j], dy = y[i] - y[j];
tm = std::max(tm, sqrt(dx * dx + dy * dy) / 2);
}
}
mind = std::min(mind, tm);
}
return mind;
}
FoxesOfTheRoundTable
Problem Details
All of the foxes must exist in the configuration, what differs is the position. This means that both the shortest and tallest fox will be there. So first imagine the shortest fox and the tallest fox in two positions of a circle and now we just need to fill the two spaces between them. There are two spaces between the shortest and tallest Fox. One of the spaces is to the left of the shortest fox (right to the tallest) and the other space is to the right of the shortest fox and the left of the tallest fox.
A nice observation here is to notice that all the foxes between the shortest and tallest one (in either direction) should be sorted in non-decreasing order. Consider this sequence: {shortest, a, b, c, d …, z, tallest}. Then (shortest <= a <= b <= … <= z <= tallest). We want the height difference between two consecutive foxes to be as little as possible, using any other will never help in that objective and will likely make it worse. Note that there are two of these spaces to fill, so this observation doesn’t make the solution trivial. We still need to pick which group should each of the Foxes be placed in.
Imagine we decide the placement of each fox in non-decreasing order. We first place the shortest Fox. We now have to decide where to place the second-shortest Fox. We can put her to the left or to the right of the first Fox. When deciding the third Fox, there will now be two already-placed foxes and we can put her to the left of the left-most fox or to the right of the right-most fox. This pattern repeats after wards, there is an already-placed left-most fox and an already-placed right-most fox. We can treat the initial case as the shortest fox being both the left-most and right-most fox. Following this approach will ensure we keep the correct ordering in both groups until we place the very last fox - the tallest one. This one will be adjacent to both the left-most and right-most fox.
We know what order to decide, but how to decide? Something that helps here is to notice that due to the constraints the final result won’t be larger than 999. So we can ask the question: “Is it possible to have `X` as the maximum difference between two adjacent Foxes?”. We can repeat this question starting with 1 as `X`, then 2, then 3 and so and so. We will eventually get the one `X` that is the smallest that allows it. (In fact, we can also use binary search, but the constraints are small enough so that this isn’t necessary).
Once we fix `X` and ask: “Is it possible to have `X` as the maximum difference between adjacent foxes?”. We can try and find a strategy that tries to build the Fox ordering in such a way that the adjacent difference never exceeds `X`. We start with the shortest Fox. Then for every next Fox we have a left-most `f` and a right-most Fox `b`. If the height of the new fox is `h`, we need to decide to add the Fox to the left (next to `f`) or to the right (next to `b`). Note that thanks to the order of the foxes, `h >= f,b`.
If `h - f > X` and `h - b > X`, then we cannot place the new Fox at all. The whole thing fails.
If `(h - f <= X)` and `(h - b <= X)`, then we can decide which group to place the Fox into. The decision needs to be made in a way that we guarantee that the process will only fail in cases where it is absolutely impossible to fill the foxes correctly.
In the other cases, we are forced to add the Fox left or right, respectively.
The final Fox, the tallest one has to be adjacent to both the left-most and right-most fox. So in that case, both `(h - f <= X)` and `(h - b <= X)` need to be true.
In all stages of the strategy, the larger `h - f` and `h - b` is, the more difficult it will be. So in each step we should try to keep the next step values for `f` and `b` as large as possible. So when there is a decision to make, we should pick to add the new fox to the side that currently has the shortest Fox. This is the solution.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
vector < int > minimalDifference(vector < int > h) {
//save the original vector before sorting, this is useful when rebuilding
// the indexes for the return.
vector < int > orig = h;
// sort it:
sort(h.begin(), h.end());
int n = h.size();
// given a maximum allowed difference:
for (int dif = 0; dif <= 1000; dif++) {
// we will use a list here because it's convenient for this algorithm.
// the "back" of the list will be the right-most fox,
// the front the left-most fox. We add new foxes to either the back
// or the front.
list < int > t;
t.push_back(h[0]);
bool bad = false;
for (int i = 1; i < n - 1; i++) {
int b = t.back(), f = t.front();
if ((h[i] - b <= dif) && (h[i] - f <= dif)) {
//must choose
if (h[i] - b > h[i] - f) {
t.push_back(h[i]);
} else {
t.push_front(h[i]);
}
} else if (h[i] - b <= dif) {
t.push_back(h[i]);
} else if (h[i] - f <= dif) {
t.push_front(h[i]);
} else {
bad = true;
}
}
// The last fox, the tallest one connect the two sides:
if ((h.back() - h[n - 1] > dif) || (h.back() - h[0] > dif)) {
bad = true;
} else {
t.push_back(h.back());
}
if (!bad) {
// list t contains a valid ordering, but it is not in the wanted
// return format. Let's translate it into indexes:
vector < int > res;
for (int x: t) {
for (int i = 0; i < n; i++) {
if (orig[i] == x) {
res.push_back(i);
orig[i] = -1;
break;
}
}
}
return res;
}
}
return {}; // unreachable code
}
A problem like this seems to call for a dynamic programming solution. The pair-wise distances might make it difficult to split the problem in sub-problems as we usually can do with trees.
What we want is the sum of all pair-wise shortest distances between nodes in the tree. Those shortest distances make it difficult to divide and conquer. But what if we find a way to calculate the sum of all pair-wise shortest distances without relying on those distances?
The key idea is to consider that the shortest path between two nodes in a tree is equal to a sequence of edges. Each time an edge is in the shortest path between two nodes, it adds 1 to the total sum. So we can calculate this: For each edge, count the number of times the edge belongs to the shortest path between two nodes of the tree. The sum of all these counts in the result we want.
Given an edge, how many shortest paths use this edge? Since we have a tree, then the edge connects two sub-trees: Let’s call them A and B. If the two nodes connected by a path belong to the same subtree (A or B), then there will be no reason to use this edge. So this edge is used in a shortest path if and only if the shortest path connects two nodes in different subtrees: one in A and one in B. There are `|A| times |B|` proper pairs of nodes where each node is in a distinct subtree.
One thing that can help us here is to assume the tree is rooted: Pick an arbitrary vertex of the tree and call it the root. Then each node `x` can represent a new sub-tree rooted at `x`. Consider an edge, we have two subtrees, `A` and `B` that appear when the edge is removed. One of `A` and `B` will be an official subtree of the rooted tree, whilst the other will be the complement of that tree. Let `s(x)` be the number of nodes in the subtree rooted at `x` (including `x`), then the total number of times the edge `(u,v)` appears in a shortest path : `s(u) * (n - s(u))`. We will do this for each edge. From here we can make a formula: The sum we are looking for is equal to `sum( s(i) * (n - s(i) ) )`
The new formula is based on `s(x)`: The total number of nodes in the subtree rooted at `x` (including `x`). This makes it easier to split the problem into subproblems: Starting from the root, for each vertex, select a value of `s(x)`, so that the sum is equal to `r` modulo `m`.
Let `f(t, r)` be a function that finds out if it is possible to make a tree of `t` nodes so that the final sum of all pairwise distances is equal to `r` modulo `m`. If it is possible, `f(t,r)` returns the minimum value for the sum of pairwise distances. If it is impossible, it should return a very large number. The solution to the main problem is `f(n,r)`.
The first node of a tree is the root. We need to forcefully add a root. The total number of nodes in this subtree will be `t`. So we say `x = r*(n - r)`. Now we can proceed to create children subtrees. We will use `g(t, r)` for the case when there is no root to be added (Because it has been already added). Since we want the overall sum to be equal to `r -= mod m` then `r_1 = (m - r) mod m` and we need to calculate `g( t - 1, r_1)`.
How to solve `g(t, r)` ? We should begin by creating a tree using some of the `t` available nodes. We need to decide how many nodes, we can try any `j` from 1 to `t` for this purpose. Then we need to decide what modulo the sum of the newly added tree should be. Then we call `f(j, r_1)` and `g(t - j, r_2)` to a) Create a tree with a root. b) Continue creating more trees to fill the real root above us. Note that `r_1 + r_2 -= r mod m`.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int getTree(int n, int m, int R) {
const int INF = 1000000000;
vector < vector < int >> f(n + 1, vector < int > (m));
vector < vector < int >> g(n + 1, vector < int > (m));
for (int r = 0; r < m; r++) {
g[0][r] = INF;
f[0][r] = INF;
}
g[0][0] = 0;
for (int t = 1; t <= n; t++) { //50
for (int r = 0; r < m; r++) {
// for f[t][r], take a root and
int x = t * (n - t);
// x + r1 = r mod m
// r1 = r - x mod m
int r1 = (r - x % m + m) % m;
f[t][r] = std::min(INF, g[t - 1][r1] + x);
g[t][r] = INF;
for (int j = 1; j <= t; j++) { //50*50
for (r1 = 0; r1 < m; r1++) { //50*50*100
int p = f[j][r1];
// r1 + r2 = r mod m
// r2 = r - r1 mod m
int r2 = (r - r1 + m) % m;
int q = g[t - j][r2];
g[t][r] = std::min(g[t][r], p + q);
}
}
}
}
return (f[n][R] >= INF) ? -1 : f[n][R];
}